import java.util.*;

class Solution04 {
    public List<String> topKFrequent(String[] words, int k) {
        // 统计每个单词出现的个数
        Map<String, Integer> hashMap = new HashMap<>();
        for (String s : words) {
            hashMap.put(s, hashMap.getOrDefault(s, 0) + 1);
        }

        // 创建一个大小为k的小根堆 自定义比较方法
        PriorityQueue<Pair<String, Integer>> q = new PriorityQueue<>(
                (a, b) -> {
                    if (a.getValue().equals(b.getValue())) // 频次相同的时候，字典序采用大根堆的方式排列
                    {
                        return b.getKey().compareTo(a.getKey());
                    }
                    return a.getValue() - b.getValue();// 采用小根堆的方式排列
                });

        // Topk的主逻辑 哈希表中的元素依次进堆
        for (Map.Entry<String, Integer> entry : hashMap.entrySet()) {
            q.offer(new Pair<>(entry.getKey(),entry.getValue()));
            if (q.size() > k) {
                q.poll();
            }
        }
        List<String> ret = new ArrayList<>();
        while(k > 0){
            ret.add(q.poll().getKey());
            k--;
        }
        Collections.reverse(ret);
        return ret;
    }
}
